package org.example.myleet.segmenttree;

public class DynamicSplitSegmentTreeFor2569 {
    private final Segment root;

    public Segment getRoot() {
        return root;
    }

    /**
     * 定义线段树控制的范围
     */
    public DynamicSplitSegmentTreeFor2569(int[] nums1) {
        int n = nums1.length;
        root = new Segment(0, n - 1);
        build(nums1, root);
    }

    private void build(int[] nums1, Segment segment) {
        if (segment.l == segment.r) {
            segment.v = nums1[segment.l];
            return;
        }
        int m = (segment.l + segment.r) / 2;
        Segment left = new Segment(segment.l, m);
        build(nums1, left);
        segment.left = left;
        Segment right = new Segment(m + 1, segment.r);
        build(nums1, right);
        segment.right = right;
        segment.v = left.v + right.v;
    }

    private void flipSegment(int l, int r, Segment segment) {
        segment.v = r - l + 1 - segment.v;
        segment.add = segment.add == 0 ? 1 : 0;
    }

    public void modify(int l, int r, int v, Segment segment) {
        if (l > r) {
            return;
        }
        if (null == segment) {
            segment = root;
        }
        if (l <= segment.l && segment.r <= r) {
            //更新的范围覆盖了整个线段，则直接修改线段的值，并标记add标签
            flipSegment(segment.l, segment.r, segment);
            return;
        }
        //更新的范围没有覆盖到整个线段，此时需要根据更新范围对应更新线段的左节点和右节点的值
        if (0 != segment.add) {
            //存在线段范围内的值需要更新，则传递到子节点上
            flipSegment(segment.l, segment.mid, segment.left);
            flipSegment(segment.mid + 1, segment.r, segment.right);
            //传递完成，线段的值更新标签归零
            segment.add = 0;
        }
        if (l <= segment.mid) {
            //更新范围覆盖到左节点，修改左子结点的值
            modify(l, r, v, segment.left);
        }
        if (r > segment.mid) {
            //更新范围覆盖到右节点，修改右子结点的值
            modify(l, r, v, segment.right);
        }
        //根据左节点和右节点的值更新本范围内的值
        segment.v = segment.left.v + segment.right.v;
    }
}
